SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Carmichael function</title>

</head>

Carmichael function

</h1>

</header>

In <a href="Number_theory" title="Number theory">number theory</a>, a branch of <a href="Mathematics" title="Mathematics">mathematics</a>, the Carmichael function λ(n) of a <a href="Positive_integer" class="mw-redirect" title="Positive integer">positive integer</a> n is the smallest positive integer m such that

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{m}\equiv 1{\pmod {n}}}</annotation>

</semantics>

</math><img src="./6295499efc8f39a0cd7ec690788edcb794eb2bde.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.245ex; height:2.843ex;" alt="{\displaystyle a^{m}\equiv 1{\pmod {n}}}" loading="lazy"></dd></dl>

holds for every integer a <a href="Coprime" class="mw-redirect" title="Coprime">coprime</a> to n. In algebraic terms, λ(n) is the <a href="Exponent_of_a_group" class="mw-redirect" title="Exponent of a group">exponent</a> of the <a href="Multiplicative_group_of_integers_modulo_n" title="Multiplicative group of integers modulo n">multiplicative group of integers modulo n</a>. As this is a <a href="Abelian_group#Finite_abelian_groups" title="Abelian group">finite abelian group</a>, there must exist an element whose <a href="Cyclic_group#Definition_and_notation" title="Cyclic group">order</a> equals the exponent, λ(n). Such an element is called a primitive λ-root modulo n.

The Carmichael function is named after the American mathematician <a href="Robert_Daniel_Carmichael" title="Robert Daniel Carmichael">Robert Carmichael</a> who defined it in 1910.<a href="#cite_note-1">[1]</a> It is also known as Carmichael's λ function, the reduced totient function, and the least universal exponent function.

The order of the multiplicative group of integers modulo n is φ(n), where φ is <a href="Euler's_totient_function" title="Euler's totient function">Euler's totient function</a>. Since the order of an element of a finite group divides the order of the group, λ(n) divides φ(n). The following table compares the first 36 values of λ(n) (sequence <a href="https://oeis.org/A002322" class="extiw external" title="oeis:A002322">A002322</a> in the <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>) and φ(n) (in bold if they are different; the values of n such that they are different are listed in <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="https://oeis.org/A033949" class="extiw external" title="oeis:A033949">A033949</a>).

<th scope="col"> n

</th>

<th scope="col">1

</th>

<th scope="col">2

</th>

<th scope="col">3

</th>

<th scope="col">4

</th>

<th scope="col">5

</th>

<th scope="col">6

</th>

<th scope="col">7

</th>

<th scope="col">8

</th>

<th scope="col">9

</th>

<th scope="col">10

</th>

<th scope="col">11

</th>

<th scope="col">12

</th>

<th scope="col">13

</th>

<th scope="col">14

</th>

<th scope="col">15

</th>

<th scope="col">16

</th>

<th scope="col">17

</th>

<th scope="col">18

</th>

<th scope="col">19

</th>

<th scope="col">20

</th>

<th scope="col">21

</th>

<th scope="col">22

</th>

<th scope="col">23

</th>

<th scope="col">24

</th>

<th scope="col">25

</th>

<th scope="col">26

</th>

<th scope="col">27

</th>

<th scope="col">28

</th>

<th scope="col">29

</th>

<th scope="col">30

</th>

<th scope="col">31

</th>

<th scope="col">32

</th>

<th scope="col">33

</th>

<th scope="col">34

</th>

<th scope="col">35

</th>

<th scope="col">36

</th></tr>

<tr>

<th scope="row"> λ(n)

</th>

<td>6

</td></tr>

<tr>

<th scope="row"> φ(n)

</th>

<td>12

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Numerical_examples">Numerical examples</h2></div>

<ul><li> n = 5. The set of numbers less than and coprime to 5 is {1,2,3,4}. Hence Euler's totient function has value φ(5) = 4 and the value of Carmichael's function, λ(5), must be a <a href="Divisor" title="Divisor">divisor</a> of 4. The divisor 1 does not satisfy the definition of Carmichael's function since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{1}\not \equiv 1{\pmod {5}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{1}\not \equiv 1{\pmod {5}}}</annotation>

</semantics>

</math><img src="./efa17f5203c037bae159f5b2a5415c20d1a9cfce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.393ex; height:3.176ex;" alt="{\displaystyle a^{1}\not \equiv 1{\pmod {5}}}" loading="lazy"> except for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\equiv 1{\pmod {5}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\equiv 1{\pmod {5}}}</annotation>

</semantics>

</math><img src="./09675d0ebd1b688db3f170176fd56eec079a901a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.337ex; height:2.843ex;" alt="{\displaystyle a\equiv 1{\pmod {5}}}" loading="lazy">. Neither does 2 since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{2}\equiv 3^{2}\equiv 4\not \equiv 1{\pmod {5}}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{2}\equiv 3^{2}\equiv 4\not \equiv 1{\pmod {5}}}</annotation>

</semantics>

</math><img src="./4343070cb68c3fe117ec99bf4e3835737c909b9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.901ex; height:3.176ex;" alt="{\displaystyle 2^{2}\equiv 3^{2}\equiv 4\not \equiv 1{\pmod {5}}}" loading="lazy">. Hence λ(5) = 4. Indeed, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1^{4}\equiv 2^{4}\equiv 3^{4}\equiv 4^{4}\equiv 1{\pmod {5}}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1^{4}\equiv 2^{4}\equiv 3^{4}\equiv 4^{4}\equiv 1{\pmod {5}}}</annotation>

</semantics>

</math><img src="./2f4e53ff0e6a069dccf4f1f350b3cdeb1597df0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.27ex; height:3.176ex;" alt="{\displaystyle 1^{4}\equiv 2^{4}\equiv 3^{4}\equiv 4^{4}\equiv 1{\pmod {5}}}" loading="lazy">. Both 2 and 3 are primitive λ-roots modulo 5 and also <a href="Primitive_root_modulo_n" title="Primitive root modulo n">primitive roots</a> modulo 5.</li>

<li> n = 8. The set of numbers less than and coprime to 8 is {1,3,5,7} . Hence φ(8) = 4 and λ(8) must be a divisor of 4. In fact λ(8) = 2 since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1^{2}\equiv 3^{2}\equiv 5^{2}\equiv 7^{2}\equiv 1{\pmod {8}}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1^{2}\equiv 3^{2}\equiv 5^{2}\equiv 7^{2}\equiv 1{\pmod {8}}}</annotation>

</semantics>

</math><img src="./b15844d04c9780bb8e86c8d878b14b10d2be661c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.27ex; height:3.176ex;" alt="{\displaystyle 1^{2}\equiv 3^{2}\equiv 5^{2}\equiv 7^{2}\equiv 1{\pmod {8}}}" loading="lazy">. The primitive λ-roots modulo 8 are 3, 5, and 7. There are no primitive roots modulo 8.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Recurrence_for_λ(n)">Recurrence for λ(n)</h2></div>

The Carmichael lambda function of a <a href="Prime_power" title="Prime power">prime power</a> can be expressed in terms of the Euler totient. Any number that is not 1 or a prime power can be written uniquely as the product of distinct prime powers, in which case λ of the product is the <a href="Least_common_multiple" title="Least common multiple">least common multiple</a> of the λ of the prime power factors. Specifically, λ(n) is given by the recurrence

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

<mtext> is 1, 2, 4, or an odd prime power,</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mtd>

<mtd>

</mrow>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

<mtd>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mtext> where </mtext>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mtext> are powers of distinct primes.</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda (n)={\begin{cases}\varphi (n)&{\text{if }}n{\text{ is 1, 2, 4, or an odd prime power,}}\\{\tfrac {1}{2}}\varphi (n)&{\text{if }}n=2^{r},\ r\geq 3,\\\operatorname {lcm} {\Bigl (}\lambda (n_{1}),\lambda (n_{2}),\ldots ,\lambda (n_{k}){\Bigr )}&{\text{if }}n=n_{1}n_{2}\ldots n_{k}{\text{ where }}n_{1},n_{2},\ldots ,n_{k}{\text{ are powers of distinct primes.}}\end{cases}}}</annotation>

</semantics>

</math><img src="./22c8c0956d8a7c78ed64aa366f84238663cc614b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.005ex; width:110.572ex; height:11.176ex;" alt="{\displaystyle \lambda (n)={\begin{cases}\varphi (n)&{\text{if }}n{\text{ is 1, 2, 4, or an odd prime power,}}\\{\tfrac {1}{2}}\varphi (n)&{\text{if }}n=2^{r},\ r\geq 3,\\\operatorname {lcm} {\Bigl (}\lambda (n_{1}),\lambda (n_{2}),\ldots ,\lambda (n_{k}){\Bigr )}&{\text{if }}n=n_{1}n_{2}\ldots n_{k}{\text{ where }}n_{1},n_{2},\ldots ,n_{k}{\text{ are powers of distinct primes.}}\end{cases}}}" loading="lazy"></dd></dl>

Euler's totient for a prime power, that is, a number pr with p prime and r ≥ 1, is given by

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (p^{r}){=}p^{r-1}(p-1).}</annotation>

</semantics>

</math><img src="./711cb78afbf95e074a10662387e57ddd3841c542.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.153ex; height:3.176ex;" alt="{\displaystyle \varphi (p^{r}){=}p^{r-1}(p-1).}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Carmichael's_theorems">Carmichael's theorems</h2></div>

Carmichael proved two theorems that, together, establish that if λ(n) is considered as defined by the recurrence of the previous section, then it satisfies the property stated in the introduction, namely that it is the smallest positive integer m such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{m}\equiv 1{\pmod {n}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{m}\equiv 1{\pmod {n}}}</annotation>

</semantics>

</math><img src="./6295499efc8f39a0cd7ec690788edcb794eb2bde.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.245ex; height:2.843ex;" alt="{\displaystyle a^{m}\equiv 1{\pmod {n}}}" loading="lazy"> for all a relatively prime to n.

/* start https://en.wikipedia.org/ */

.mw-parser-output .math_theorem{margin:1em 2em;padding:0.5em 1em 0.4em;border:1px solid #aaa;overflow:hidden}@media(max-width:500px){.mw-parser-output .math_theorem{margin:1em 0em;padding:0.5em 0.5em 0.4em}}

/* end https://en.wikipedia.org/ */

</style><div class="math_theorem" style="">

Theorem 1—If a is relatively prime to n then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}</annotation>

</semantics>

</math><img src="./2e475506bcb72caae57599e0ccafa7efe023be9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.026ex; height:3.343ex;" alt="{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}" loading="lazy">.<a href="#cite_note-2">[2]</a>

</div>

This implies that the order of every element of the multiplicative group of integers modulo n divides λ(n). Carmichael calls an element a for which <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{\lambda (n)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{\lambda (n)}}</annotation>

</semantics>

</math><img src="./473ca65248018952ce1e62cb03f0352b8924b2ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.686ex; height:2.843ex;" alt="{\displaystyle a^{\lambda (n)}}" loading="lazy"> is the least power of a congruent to 1 (mod n) a primitive λ-root modulo n.<a href="#cite_note-3">[3]</a> (This is not to be confused with a <a href="Primitive_root_modulo_n" title="Primitive root modulo n">primitive root modulo n</a>, which Carmichael sometimes refers to as a primitive <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi }</annotation>

</semantics>

</math><img src="./33ee699558d09cf9d653f6351f9fda0b2f4aaa3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.52ex; height:2.176ex;" alt="{\displaystyle \varphi }" loading="lazy">-root modulo n.)

Theorem 2—For every positive integer n there exists a primitive λ-root modulo n. Moreover, if g is such a root, then there are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (\lambda (n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (\lambda (n))}</annotation>

</semantics>

</math><img src="./51437c7e1b33eb915c3498ada17541d57fa725c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.889ex; height:2.843ex;" alt="{\displaystyle \varphi (\lambda (n))}" loading="lazy"> primitive λ-roots that are congruent to powers of g.<a href="#cite_note-4">[4]</a>

</div>

If g is one of the primitive λ-roots guaranteed by the theorem, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g^{m}\equiv 1{\pmod {n}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g^{m}\equiv 1{\pmod {n}}}</annotation>

</semantics>

</math><img src="./c63ff9fb4421a3577195c1394651e87c70b49c59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.133ex; height:2.843ex;" alt="{\displaystyle g^{m}\equiv 1{\pmod {n}}}" loading="lazy"> has no positive integer solutions m less than λ(n), showing that there is no positive m < λ(n) such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{m}\equiv 1{\pmod {n}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{m}\equiv 1{\pmod {n}}}</annotation>

</semantics>

</math><img src="./6295499efc8f39a0cd7ec690788edcb794eb2bde.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.245ex; height:2.843ex;" alt="{\displaystyle a^{m}\equiv 1{\pmod {n}}}" loading="lazy"> for all a relatively prime to n.

The second statement of Theorem 2 does not imply that all primitive λ-roots modulo n are congruent to powers of a single root g.<a href="#cite_note-5">[5]</a> For example, if n = 15, then λ(n) = 4 while <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (n)=8}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (n)=8}</annotation>

</semantics>

</math><img src="./2036c0ac806e07b8c751fbac720051359cd53670.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.985ex; height:2.843ex;" alt="{\displaystyle \varphi (n)=8}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (\lambda (n))=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (\lambda (n))=2}</annotation>

</semantics>

</math><img src="./53bdbcac5e38bad232b72dac87c50f9aa3e77c9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.15ex; height:2.843ex;" alt="{\displaystyle \varphi (\lambda (n))=2}" loading="lazy">. There are four primitive λ-roots modulo 15, namely 2, 7, 8, and 13 as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\equiv 2^{4}\equiv 8^{4}\equiv 7^{4}\equiv 13^{4}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\equiv 2^{4}\equiv 8^{4}\equiv 7^{4}\equiv 13^{4}}</annotation>

</semantics>

</math><img src="./d678d8b242ba198634a86b6f0c86870884a869f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:23.586ex; height:2.676ex;" alt="{\displaystyle 1\equiv 2^{4}\equiv 8^{4}\equiv 7^{4}\equiv 13^{4}}" loading="lazy">. The roots 2 and 8 are congruent to powers of each other and the roots 7 and 13 are congruent to powers of each other, but neither 7 nor 13 is congruent to a power of 2 or 8 and vice versa. The other four elements of the multiplicative group modulo 15, namely 1, 4 (which satisfies <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 4\equiv 2^{2}\equiv 8^{2}\equiv 7^{2}\equiv 13^{2}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 4\equiv 2^{2}\equiv 8^{2}\equiv 7^{2}\equiv 13^{2}}</annotation>

</semantics>

</math><img src="./9074d6877ba22a2a1dac0dd4ab2419b028e9df0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:23.586ex; height:2.676ex;" alt="{\displaystyle 4\equiv 2^{2}\equiv 8^{2}\equiv 7^{2}\equiv 13^{2}}" loading="lazy">), 11, and 14, are not primitive λ-roots modulo 15.

For a contrasting example, if n = 9, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda (n)=\varphi (n)=6}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda (n)=\varphi (n)=6}</annotation>

</semantics>

</math><img src="./54e6711ca9d76332b47ccc8d3d9e4ea49ba75ccc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.643ex; height:2.843ex;" alt="{\displaystyle \lambda (n)=\varphi (n)=6}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (\lambda (n))=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (\lambda (n))=2}</annotation>

</semantics>

</math><img src="./53bdbcac5e38bad232b72dac87c50f9aa3e77c9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.15ex; height:2.843ex;" alt="{\displaystyle \varphi (\lambda (n))=2}" loading="lazy">. There are two primitive λ-roots modulo 9, namely 2 and 5, each of which is congruent to the fifth power of the other. They are also both primitive <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi }</annotation>

</semantics>

</math><img src="./33ee699558d09cf9d653f6351f9fda0b2f4aaa3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.52ex; height:2.176ex;" alt="{\displaystyle \varphi }" loading="lazy">-roots modulo 9.

<div class="mw-heading mw-heading2"><h2 id="Properties_of_the_Carmichael_function">Properties of the Carmichael function</h2></div>

In this section, an <a href="Integer" title="Integer">integer</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is divisible by a nonzero integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> if there exists an integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=km}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=km}</annotation>

</semantics>

</math><img src="./3a1645879dc35ab812df3d8928505ac28d8870f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.745ex; height:2.176ex;" alt="{\displaystyle n=km}" loading="lazy">. This is written as

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\mid n.}</annotation>

</semantics>

</math><img src="./5ab022dece84389d986d53e94e1da0d5ef7229a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.019ex; height:2.843ex;" alt="{\displaystyle m\mid n.}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="A_consequence_of_minimality_of_λ(n)">A consequence of minimality of λ(n)</h3></div>

Suppose am ≡ 1 (mod n) for all numbers a coprime with n. Then λ(n) | m.

Proof: If m = kλ(n) + r with 0 ≤ r < λ(n), then

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{r}=1^{k}\cdot a^{r}\equiv \left(a^{\lambda (n)}\right)^{k}\cdot a^{r}=a^{k\lambda (n)+r}=a^{m}\equiv 1{\pmod {n}}}</annotation>

</semantics>

</math><img src="./b149c64e0b0d5121a4c0d999a25eda1567af9eda.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:58.971ex; height:5.343ex;" alt="{\displaystyle a^{r}=1^{k}\cdot a^{r}\equiv \left(a^{\lambda (n)}\right)^{k}\cdot a^{r}=a^{k\lambda (n)+r}=a^{m}\equiv 1{\pmod {n}}}" loading="lazy"></dd></dl>

for all numbers a coprime with n. It follows that r = 0 since r < λ(n) and λ(n) is the minimal positive exponent for which the congruence holds for all a coprime with n.

<div class="mw-heading mw-heading3"><h3 id="λ(n)_divides_φ(n)"> λ(n) divides φ(n)</h3></div>

This follows from elementary <a href="Group_theory" title="Group theory">group theory</a>, because the exponent of any <a href="Finite_group" title="Finite group">finite group</a> must divide the order of the group. λ(n) is the exponent of the multiplicative group of integers modulo n while φ(n) is the order of that group. In particular, the two must be equal in the cases where the multiplicative group is cyclic due to the existence of a <a href="Primitive_root_modulo_n" title="Primitive root modulo n">primitive root</a>, which is the case for odd prime powers.

We can thus view Carmichael's theorem as a sharpening of <a href="Euler's_theorem" title="Euler's theorem">Euler's theorem</a>.

<div class="mw-heading mw-heading3"><h3 id="Divisibility">Divisibility</h3></div>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\,|\,b\Rightarrow \lambda (a)\,|\,\lambda (b)}</annotation>

</semantics>

</math><img src="./448a742da33b60ccbf31c74c04eb41e8697f73ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.24ex; height:2.843ex;" alt="{\displaystyle a\,|\,b\Rightarrow \lambda (a)\,|\,\lambda (b)}" loading="lazy"></dd></dl>

Proof.

By definition, for any integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gcd(k,b)=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gcd(k,b)=1}</annotation>

</semantics>

</math><img src="./249744635d33a732fa004574ae9d19827a2d24a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.8ex; height:2.843ex;" alt="{\displaystyle \gcd(k,b)=1}" loading="lazy"> (and thus also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gcd(k,a)=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gcd(k,a)=1}</annotation>

</semantics>

</math><img src="./6b507ceccc912e2a211c8f5f235d90654b977db7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.033ex; height:2.843ex;" alt="{\displaystyle \gcd(k,a)=1}" loading="lazy">), we have that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b\,|\,(k^{\lambda (b)}-1)}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\,|\,(k^{\lambda (b)}-1)}</annotation>

</semantics>

</math><img src="./5d87ac2c62fa68510edaa1899e8f77c7fc33ef79.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.617ex; height:3.343ex;" alt="{\displaystyle b\,|\,(k^{\lambda (b)}-1)}" loading="lazy"> , and therefore <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\,|\,(k^{\lambda (b)}-1)}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\,|\,(k^{\lambda (b)}-1)}</annotation>

</semantics>

</math><img src="./a5e61e1f9cb41b188fef2f775478707ab9ee2301.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.85ex; height:3.343ex;" alt="{\displaystyle a\,|\,(k^{\lambda (b)}-1)}" loading="lazy">. This establishes that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k^{\lambda (b)}\equiv 1{\pmod {a}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k^{\lambda (b)}\equiv 1{\pmod {a}}}</annotation>

</semantics>

</math><img src="./61e6c2d9be9b3c87e275e9f080c142af12791836.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.561ex; height:3.343ex;" alt="{\displaystyle k^{\lambda (b)}\equiv 1{\pmod {a}}}" loading="lazy"> for all k relatively prime to a. By the consequence of minimality proved above, we have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda (a)\,|\,\lambda (b)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda (a)\,|\,\lambda (b)}</annotation>

</semantics>

</math><img src="./86fe3c4dd2a26935e4497431aca57d92f9a2cb2b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.977ex; height:2.843ex;" alt="{\displaystyle \lambda (a)\,|\,\lambda (b)}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Composition">Composition</h3></div>

For all positive integers a and b it holds that

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda (\mathrm {lcm} (a,b))=\mathrm {lcm} (\lambda (a),\lambda (b))}</annotation>

</semantics>

</math><img src="./a94bb6137a29ab109abc96b5f81c79ea85ecb241.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.963ex; height:2.843ex;" alt="{\displaystyle \lambda (\mathrm {lcm} (a,b))=\mathrm {lcm} (\lambda (a),\lambda (b))}" loading="lazy">.</dd></dl>

This is an immediate consequence of the recurrence for the Carmichael function.

<div class="mw-heading mw-heading3"><h3 id="Exponential_cycle_length">Exponential cycle length</h3></div>

If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{\mathrm {max} }=\max _{i}\{r_{i}\}}">

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{\mathrm {max} }=\max _{i}\{r_{i}\}}</annotation>

</semantics>

</math><img src="./8d04b325740d26119d2d24e8fb3569634c9d20b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:15.937ex; height:4.009ex;" alt="{\displaystyle r_{\mathrm {max} }=\max _{i}\{r_{i}\}}" loading="lazy"> is the biggest exponent in the prime factorization <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}}</annotation>

</semantics>

</math><img src="./c2c65ea3b23584241e69dd75a2bd439af0e03ca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:16.943ex; height:3.176ex;" alt="{\displaystyle n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}}" loading="lazy"> of n, then for all a (including those not coprime to n) and all r ≥ rmax,

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{r}\equiv a^{\lambda (n)+r}{\pmod {n}}.}</annotation>

</semantics>

</math><img src="./c010538ffaab692c767f4ae2cbe2e8e22de90f0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.734ex; height:3.343ex;" alt="{\displaystyle a^{r}\equiv a^{\lambda (n)+r}{\pmod {n}}.}" loading="lazy"></dd></dl>

In particular, for <a href="Square-free_integer" title="Square-free integer">square-free</a> n ( rmax = 1), for all a we have

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\equiv a^{\lambda (n)+1}{\pmod {n}}.}</annotation>

</semantics>

</math><img src="./8b6f43d890e1e43807d5c56ea3f2c250cda0dd65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.84ex; height:3.343ex;" alt="{\displaystyle a\equiv a^{\lambda (n)+1}{\pmod {n}}.}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Average_value">Average value</h3></div>

For any n ≥ 16:<a href="#cite_note-6">[6]</a><a href="#cite_note-HBII194-7">[7]</a>

<mfrac>

</mfrac>

</mrow>

</mrow>

</munder>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{n}}\sum _{i\leq n}\lambda (i)={\frac {n}{\ln n}}e^{B(1+o(1))\ln \ln n/(\ln \ln \ln n)}}</annotation>

</semantics>

</math><img src="./978fdf6ffcb4b74988f74f3d15438bea0304d0d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:40.077ex; height:6.509ex;" alt="{\displaystyle {\frac {1}{n}}\sum _{i\leq n}\lambda (i)={\frac {n}{\ln n}}e^{B(1+o(1))\ln \ln n/(\ln \ln \ln n)}}" loading="lazy"></dd></dl>

(called Erdős approximation in the following) with the constant

<msup>

</mrow>

</msup>

</mrow>

</munder>

<mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B:=e^{-\gamma }\prod _{p\in \mathbb {P} }\left({1-{\frac {1}{(p-1)^{2}(p+1)}}}\right)\approx 0.34537}</annotation>

</semantics>

</math><img src="./44b1d15761823a5fea5e3f4a63c2dd5a89c014a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:46.737ex; height:7.009ex;" alt="{\displaystyle B:=e^{-\gamma }\prod _{p\in \mathbb {P} }\left({1-{\frac {1}{(p-1)^{2}(p+1)}}}\right)\approx 0.34537}" loading="lazy"></dd></dl>

and γ ≈ 0.57721, the <a href="Euler%E2%80%93Mascheroni_constant" class="mw-redirect" title="Euler–Mascheroni constant">Euler–Mascheroni constant</a>.

The following table gives some overview over the first 226 – 1 = 67108863 values of the λ function, for both, the exact average and its Erdős-approximation.

Additionally given is some overview over the more easily accessible “logarithm over logarithm” values LoL(n) := <style data-mw-deduplicate="TemplateStyles:r1214402035">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}

/* end https://en.wikipedia.org/ */

</style>⁠ln λ(n)/ln n⁠ with

There, the table entry in row number 26 at column

indicates that 60.49% (≈ 40000000) of the integers 1 ≤ n ≤ 67108863 have λ(n) > n⁠4/5⁠ meaning that the majority of the λ values is exponential in the length l := log2(n) of the input n, namely

<msup>

<mrow>

<msup>

<mfrac>

</mfrac>

</mrow>

</msup>

</mrow>

</mrow>

</msup>

<msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

<msup>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mfrac>

</mfrac>

</mrow>

</msup>

<msup>

<mfrac>

</mfrac>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left(2^{\frac {4}{5}}\right)^{l}=2^{\frac {4l}{5}}=\left(2^{l}\right)^{\frac {4}{5}}=n^{\frac {4}{5}}.}</annotation>

</semantics>

</math><img src="./2263292ffc6e56ae950699aa05f06f93d98c9d70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:29.161ex; height:6.676ex;" alt="{\displaystyle \left(2^{\frac {4}{5}}\right)^{l}=2^{\frac {4l}{5}}=\left(2^{l}\right)^{\frac {4}{5}}=n^{\frac {4}{5}}.}" loading="lazy"></dd></dl>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i\leq n}\lambda (i)}</annotation>

</semantics>

</math><img src="./89b1a5b1ad35c4394835b0cb6ef88afe2594903d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:7.709ex; height:5.676ex;" alt="{\displaystyle \sum _{i\leq n}\lambda (i)}" loading="lazy"></th>

<th>average <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {1}{n}}\sum _{i\leq n}\lambda (i)}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{n}}\sum _{i\leq n}\lambda (i)}</annotation>

</semantics>

</math><img src="./8976a46d0f45aa901d7cb4eaff88667cbc620518.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:9.919ex; height:5.676ex;" alt="{\displaystyle {\tfrac {1}{n}}\sum _{i\leq n}\lambda (i)}" loading="lazy"></th>

<th>Erdős average</th>

<th>Erdős / exact average</th>

<th> LoL average</th>

<th>% LoL > ⁠7/8⁠

</th></tr>

<tr>

<td>35.48

</td></tr>

<tr>

<td>30.16

</td></tr>

<tr>

<td>27.56

</td></tr>

<tr>

<td>23.53

</td></tr>

<tr>

<td>25.05

</td></tr>

<tr>

<td>26.98

</td></tr>

<tr>

<td>27.70

</td></tr>

<tr>

<td>28.11

</td></tr>

<tr>

<td>28.60

</td></tr>

<tr>

<td>29.52

</td></tr>

<tr>

<td>29.15

</td></tr>

<tr>

<td>28.17

</td></tr>

<tr>

<td>29.55

</td></tr>

<tr>

<td>30.67

</td></tr>

<tr>

<td>31.45

</td></tr>

<tr>

<td>31.83

</td></tr>

<tr>

<td>32.18

</td></tr>

<tr>

<td>33.65

</td></tr>

<tr>

<td>34.32

</td></tr>

<tr>

<td>34.43

</td></tr>

<tr>

<td>35.76

</td></tr>

<tr>

<td>36.73

</td></tr></tbody></table></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Prevailing_interval">Prevailing interval</h3></div>

For all numbers N and all but o(N)<a href="#cite_note-8">[8]</a> positive integers n ≤ N (a "prevailing" majority):

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda (n)={\frac {n}{(\ln n)^{\ln \ln \ln n+A+o(1)}}}}</annotation>

</semantics>

</math><img src="./91268eb20942e09421cb5ee919ee12eaab785b44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:27.206ex; height:5.676ex;" alt="{\displaystyle \lambda (n)={\frac {n}{(\ln n)^{\ln \ln \ln n+A+o(1)}}}}" loading="lazy"></dd></dl>

with the constant<a href="#cite_note-HBII194-7">[7]</a>

</mrow>

</munder>

<mfrac>

<mrow>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A:=-1+\sum _{p\in \mathbb {P} }{\frac {\ln p}{(p-1)^{2}}}\approx 0.2269688}</annotation>

</semantics>

</math><img src="./3ed0a5fe9830d69d7dd117ca86c2b4a646ce9f33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:36.958ex; height:6.843ex;" alt="{\displaystyle A:=-1+\sum _{p\in \mathbb {P} }{\frac {\ln p}{(p-1)^{2}}}\approx 0.2269688}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Lower_bounds">Lower bounds</h3></div>

For any sufficiently large number N and for any Δ ≥ (ln ln N)3, there are at most

<mrow>

<mrow>

<msup>

<mfrac>

</mfrac>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\exp \left(-0.69(\Delta \ln \Delta )^{\frac {1}{3}}\right)}</annotation>

</semantics>

</math><img src="./98b2a51e00effb08a01362cf15844d9b73915092.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:25.497ex; height:6.176ex;" alt="{\displaystyle N\exp \left(-0.69(\Delta \ln \Delta )^{\frac {1}{3}}\right)}" loading="lazy"></dd></dl>

positive integers n ≤ N such that λ(n) ≤ ne−Δ.<a href="#cite_note-9">[9]</a>

<div class="mw-heading mw-heading3"><h3 id="Minimal_order">Minimal order</h3></div>

For any sequence n1 < n2 < n3 < ⋯ of positive integers, any constant 0 < c < ⁠1/ln 2⁠, and any sufficiently large i:<a href="#cite_note-Theorem_1_in_Erdős_(1991)-10">[10]</a><a href="#cite_note-HBII193-11">[11]</a>

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda (n_{i})>\left(\ln n_{i}\right)^{c\ln \ln \ln n_{i}}.}">

<msub>

</mrow>

</msub>

<msup>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda (n_{i})>\left(\ln n_{i}\right)^{c\ln \ln \ln n_{i}}.}</annotation>

</semantics>

</math><img src="./a144710ef62f61eff3056f1ce818d0b1bbd90cb2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.652ex; height:3.343ex;" alt="{\displaystyle \lambda (n_{i})>\left(\ln n_{i}\right)^{c\ln \ln \ln n_{i}}.}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Small_values">Small values</h3></div>

For a constant c and any sufficiently large positive A, there exists an integer n > A such that<a href="#cite_note-HBII193-11">[11]</a>

<msup>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda (n)<\left(\ln A\right)^{c\ln \ln \ln A}.}</annotation>

</semantics>

</math><img src="./f6d97f7da496c4eb01000532f578bd837d225b2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.023ex; height:3.343ex;" alt="{\displaystyle \lambda (n)<\left(\ln A\right)^{c\ln \ln \ln A}.}" loading="lazy"></dd></dl>

Moreover, n is of the form

</mrow>

</munder>

</mrow>

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=\mathop {\prod _{q\in \mathbb {P} }} _{(q-1)|m}q}</annotation>

</semantics>

</math><img src="./939d7257aa91af9a9cb572c1c708fd953411d211.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.671ex; width:11.986ex; height:8.176ex;" alt="{\displaystyle n=\mathop {\prod _{q\in \mathbb {P} }} _{(q-1)|m}q}" loading="lazy"></dd></dl>

for some square-free integer m < (ln A)c ln ln ln A.<a href="#cite_note-Theorem_1_in_Erdős_(1991)-10">[10]</a>

<div class="mw-heading mw-heading3"><h3 id="Image_of_the_function">Image of the function</h3></div>

The set of values of the Carmichael function has counting function<a href="#cite_note-12">[12]</a>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {x}{(\ln x)^{\eta +o(1)}}},}</annotation>

</semantics>

</math><img src="./4ef2e928429f111c920be5cb5322b37be124686d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:12.185ex; height:5.676ex;" alt="{\displaystyle {\frac {x}{(\ln x)^{\eta +o(1)}}},}" loading="lazy"></dd></dl>

where

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \eta =1-{\frac {1+\ln \ln 2}{\ln 2}}\approx 0.08607}</annotation>

</semantics>

</math><img src="./40abee8e1550e7653459660d55c3a9f5f288a3f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:29.645ex; height:5.343ex;" alt="{\displaystyle \eta =1-{\frac {1+\ln \ln 2}{\ln 2}}\approx 0.08607}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Use_in_cryptography">Use in cryptography</h2></div>

The Carmichael function is important in <a href="Cryptography" title="Cryptography">cryptography</a> due to its use in the <a href="RSA_(cryptosystem)" class="mw-redirect" title="RSA (cryptosystem)">RSA encryption algorithm</a>.

<div class="mw-heading mw-heading2"><h2 id="Proof_of_Theorem_1">Proof of Theorem 1</h2></div>

For n = p, a prime, Theorem 1 is equivalent to <a href="Fermat's_little_theorem" title="Fermat's little theorem">Fermat's little theorem</a>:

<msup>

</mrow>

</msup>

</mrow>

</mrow>

<mtext> coprime to </mtext>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{p-1}\equiv 1{\pmod {p}}\qquad {\text{for all }}a{\text{ coprime to }}p.}</annotation>

</semantics>

</math><img src="./5750f0b1972a8112485fde8b9a84dba4772e4ec9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:45.422ex; height:3.176ex;" alt="{\displaystyle a^{p-1}\equiv 1{\pmod {p}}\qquad {\text{for all }}a{\text{ coprime to }}p.}" loading="lazy"></dd></dl>

For prime powers pr, r > 1, if

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{p^{r-1}(p-1)}=1+hp^{r}}</annotation>

</semantics>

</math><img src="./9bfbfa3f96545ef4f5eabab73d670eb00e822a2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:19.551ex; height:3.343ex;" alt="{\displaystyle a^{p^{r-1}(p-1)}=1+hp^{r}}" loading="lazy"></dd></dl>

holds for some integer h, then raising both sides to the power p gives

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

<msup>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{p^{r}(p-1)}=1+h'p^{r+1}}</annotation>

</semantics>

</math><img src="./5428c7674e01684040cdb2d64baba27d74725ca1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:20.631ex; height:3.176ex;" alt="{\displaystyle a^{p^{r}(p-1)}=1+h'p^{r+1}}" loading="lazy"></dd></dl>

for some other integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h'}</annotation>

</semantics>

</math><img src="./6b9dea8e11793a3d64d2be5b4a15f479363e063c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle h'}" loading="lazy">. By induction it follows that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{\varphi (p^{r})}\equiv 1{\pmod {p^{r}}}}">

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{\varphi (p^{r})}\equiv 1{\pmod {p^{r}}}}</annotation>

</semantics>

</math><img src="./6c23aeb25cc2ed70a2d4195559e3ac2f2ded2e39.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.498ex; height:3.343ex;" alt="{\displaystyle a^{\varphi (p^{r})}\equiv 1{\pmod {p^{r}}}}" loading="lazy"> for all a relatively prime to p and hence to pr. This establishes the theorem for n = 4 or any odd prime power.

<div class="mw-heading mw-heading3"><h3 id="Sharpening_the_result_for_higher_powers_of_two">Sharpening the result for higher powers of two</h3></div>

For a coprime to (powers of) 2 we have a = 1 + 2h2 for some integer h2. Then,

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{2}=1+4h_{2}(h_{2}+1)=1+8{\binom {h_{2}+1}{2}}=:1+8h_{3}}</annotation>

</semantics>

</math><img src="./02b86b199d755fd6e4a715f56a51555daae3fe74.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:50.531ex; height:6.176ex;" alt="{\displaystyle a^{2}=1+4h_{2}(h_{2}+1)=1+8{\binom {h_{2}+1}{2}}=:1+8h_{3}}" loading="lazy">,</dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{3}}</annotation>

</semantics>

</math><img src="./e9b7b4e24b0477e3270e7c640a73be1a8dc7f300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.393ex; height:2.509ex;" alt="{\displaystyle h_{3}}" loading="lazy"> is an integer. With r = 3, this is written

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{2^{r-2}}=1+2^{r}h_{r}.}</annotation>

</semantics>

</math><img src="./9ffa57f4c21b2ef7fe9da5aac53c3445b8628bd5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.953ex; height:3.343ex;" alt="{\displaystyle a^{2^{r-2}}=1+2^{r}h_{r}.}" loading="lazy"></dd></dl>

Squaring both sides gives

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

<msup>

<mrow>

<mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{2^{r-1}}=\left(1+2^{r}h_{r}\right)^{2}=1+2^{r+1}\left(h_{r}+2^{r-1}h_{r}^{2}\right)=:1+2^{r+1}h_{r+1},}</annotation>

</semantics>

</math><img src="./6f75f71f30cda75cba02969e915472e02730da9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:61.853ex; height:3.676ex;" alt="{\displaystyle a^{2^{r-1}}=\left(1+2^{r}h_{r}\right)^{2}=1+2^{r+1}\left(h_{r}+2^{r-1}h_{r}^{2}\right)=:1+2^{r+1}h_{r+1},}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{r+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{r+1}}</annotation>

</semantics>

</math><img src="./67859e1ec8bd8efa924407dcab6ffa3e01a0454e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.413ex; height:2.509ex;" alt="{\displaystyle h_{r+1}}" loading="lazy"> is an integer. It follows by induction that

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

<msup>

<mfrac>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{2^{r-2}}=a^{{\frac {1}{2}}\varphi (2^{r})}\equiv 1{\pmod {2^{r}}}}</annotation>

</semantics>

</math><img src="./e9bf82c2beed53c3ec8247796c0624939e3d5772.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.843ex; height:4.009ex;" alt="{\displaystyle a^{2^{r-2}}=a^{{\frac {1}{2}}\varphi (2^{r})}\equiv 1{\pmod {2^{r}}}}" loading="lazy"></dd></dl>

for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\geq 3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\geq 3}</annotation>

</semantics>

</math><img src="./c00042b0f5d6d3e14ffd54a53bf56e85de256386.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.31ex; height:2.343ex;" alt="{\displaystyle r\geq 3}" loading="lazy"> and all a coprime to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{r}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{r}}</annotation>

</semantics>

</math><img src="./c7f5f9125e1c1d0ac48d810ee16bfe95c6dabcad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.136ex; height:2.343ex;" alt="{\displaystyle 2^{r}}" loading="lazy">.<a href="#cite_note-13">[13]</a>

<div class="mw-heading mw-heading3"><h3 id="Integers_with_multiple_prime_factors">Integers with multiple prime factors</h3></div>

By the <a href="Unique_factorization_theorem" class="mw-redirect" title="Unique factorization theorem">unique factorization theorem</a>, any n > 1 can be written in a unique way as

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}}</annotation>

</semantics>

</math><img src="./c2c65ea3b23584241e69dd75a2bd439af0e03ca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:16.943ex; height:3.176ex;" alt="{\displaystyle n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}}" loading="lazy"></dd></dl>

where p1 < p2 < ... < pk are primes and r1, r2, ..., rk are positive integers. The results for prime powers establish that, for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq j\leq k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq j\leq k}</annotation>

</semantics>

</math><img src="./fe6213470ed1ea7817e7bec06ffa56be9f5e7721.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.529ex; height:2.509ex;" alt="{\displaystyle 1\leq j\leq k}" loading="lazy">,

<msup>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

</msup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

</mrow>

<mtext> coprime to </mtext>

</mrow>

<mtext> and hence to </mtext>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{\lambda \left(p_{j}^{r_{j}}\right)}\equiv 1{\pmod {p_{j}^{r_{j}}}}\qquad {\text{for all }}a{\text{ coprime to }}n{\text{ and hence to }}p_{i}^{r_{i}}.}</annotation>

</semantics>

</math><img src="./0cd88a7a773d8d0c38db41bba9e0c85482840f07.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:66.192ex; height:4.843ex;" alt="{\displaystyle a^{\lambda \left(p_{j}^{r_{j}}\right)}\equiv 1{\pmod {p_{j}^{r_{j}}}}\qquad {\text{for all }}a{\text{ coprime to }}n{\text{ and hence to }}p_{i}^{r_{i}}.}" loading="lazy"></dd></dl>

From this it follows that

<msup>

</mrow>

</msup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

</mrow>

<mtext> coprime to </mtext>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {p_{j}^{r_{j}}}}\qquad {\text{for all }}a{\text{ coprime to }}n,}</annotation>

</semantics>

</math><img src="./cc8fc2fdd80fdf9807592b49e021e75247c6ec90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:47.631ex; height:3.843ex;" alt="{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {p_{j}^{r_{j}}}}\qquad {\text{for all }}a{\text{ coprime to }}n,}" loading="lazy"></dd></dl>

where, as given by the recurrence,

</mrow>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda (n)=\operatorname {lcm} {\Bigl (}\lambda \left(p_{1}^{r_{1}}\right),\lambda \left(p_{2}^{r_{2}}\right),\ldots ,\lambda \left(p_{k}^{r_{k}}\right){\Bigr )}.}</annotation>

</semantics>

</math><img src="./07d5aca1ad5585c12ba06ad8bcb71b64f5492e37.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:42.383ex; height:4.843ex;" alt="{\displaystyle \lambda (n)=\operatorname {lcm} {\Bigl (}\lambda \left(p_{1}^{r_{1}}\right),\lambda \left(p_{2}^{r_{2}}\right),\ldots ,\lambda \left(p_{k}^{r_{k}}\right){\Bigr )}.}" loading="lazy"></dd></dl>

From the <a href="Chinese_remainder_theorem" title="Chinese remainder theorem">Chinese remainder theorem</a> one concludes that

<msup>

</mrow>

</msup>

</mrow>

</mrow>

<mtext> coprime to </mtext>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}\qquad {\text{for all }}a{\text{ coprime to }}n.}</annotation>

</semantics>

</math><img src="./175e258a123ae4c273200601470cfaf46be4f3c4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:46.169ex; height:3.343ex;" alt="{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}\qquad {\text{for all }}a{\text{ coprime to }}n.}" loading="lazy"></dd></dl>

<ul><li><a href="Carmichael_number" title="Carmichael number">Carmichael number</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCarmichael1910" class="citation journal cs1">Carmichael, Robert Daniel (1910). <a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0002-9904-1910-01892-9">"Note on a new number theory function"</a>. Bulletin of the American Mathematical Society. 16 (5): 232–238. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0002-9904-1910-01892-9">10.1090/S0002-9904-1910-01892-9</a>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> Carmichael (1914) p.40

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> Carmichael (1914) p.54

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> Carmichael (1914) p.55

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> Carmichael (1914) p.56

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> Theorem 3 in Erdős (1991)

</li>

<li id="cite_note-HBII194-7">^ <a href="#cite_ref-HBII194_7-0">a</a> <a href="#cite_ref-HBII194_7-1">b</a> Sándor & Crstici (2004) p.194

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> Theorem 2 in Erdős (1991) 3. Normal order. (p.365)

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> Theorem 5 in Friedlander (2001)

</li>

<li id="cite_note-Theorem_1_in_Erdős_(1991)-10">^ <a href="#cite_ref-Theorem_1_in_Erdős_(1991)_10-0">a</a> <a href="#cite_ref-Theorem_1_in_Erdős_(1991)_10-1">b</a> Theorem 1 in Erdős (1991)

</li>

<li id="cite_note-HBII193-11">^ <a href="#cite_ref-HBII193_11-0">a</a> <a href="#cite_ref-HBII193_11-1">b</a> Sándor & Crstici (2004) p.193

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFFordLucaPomerance2014" class="citation journal cs1">Ford, Kevin; Luca, Florian; Pomerance, Carl (27 August 2014). "The image of Carmichael's λ-function". Algebra & Number Theory. 8 (8): 2009–2026. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1408.6506">1408.6506</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2140%2Fant.2014.8.2009">10.2140/ant.2014.8.2009</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:50397623">50397623</a>.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> Carmichael (1914) pp.38–39

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFErdősPomeranceSchmutz1991" class="citation journal cs1"><a href="Paul_Erd%C5%91s" title="Paul Erdős">Erdős, Paul</a>; <a href="Carl_Pomerance" title="Carl Pomerance">Pomerance, Carl</a>; Schmutz, Eric (1991). <a rel="nofollow" class="external text" href="https://doi.org/10.4064%2Faa-58-4-363-385">"Carmichael's lambda function"</a>. Acta Arithmetica. 58 (4): 363–385. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4064%2Faa-58-4-363-385">10.4064/aa-58-4-363-385</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0065-1036">0065-1036</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1121092">1121092</a>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0734.11047">0734.11047</a>.</cite></li>

<li><cite id="CITEREFFriedlanderPomeranceShparlinski2001" class="citation journal cs1"><a href="John_Friedlander" title="John Friedlander">Friedlander, John B.</a>; Pomerance, Carl; Shparlinski, Igor E. (2001). <a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fs0025-5718-00-01282-5">"Period of the power generator and small values of the Carmichael function"</a>. Mathematics of Computation. 70 (236): 1591–1605, 1803–1806. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fs0025-5718-00-01282-5">10.1090/s0025-5718-00-01282-5</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0025-5718">0025-5718</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1836921">1836921</a>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1029.11043">1029.11043</a>.</cite></li>

<li><cite id="CITEREFSándorCrstici2004" class="citation book cs1">Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. pp. 32–36, 193–195. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4020-2546-4</bdi>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1079.11001">1079.11001</a>.</cite></li>

/* start https://en.wikipedia.org/ */

.mw-parser-output .citation{word-wrap:break-word}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}

/* end https://en.wikipedia.org/ */

</style>Carmichael, Robert D. [1914]. <a rel="nofollow" class="external text" href="https://gutenberg.org/ebooks/13693">The Theory of Numbers</a> at <a href="Project_Gutenberg" title="Project Gutenberg">Project Gutenberg</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Totient_function16" style="padding:3px"><table class="nowraplinks mw-collapsible uncollapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Totient_function16" style="font-size:114%;margin:0 4em">Totient function</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Euler's_totient_function" title="Euler's totient function">Euler's totient function</a> φ(n)</li>

<li><a href="Jordan's_totient_function" title="Jordan's totient function">Jordan's totient function</a> Jk(n)</li>

<li> (reduced totient function) λ(n)</li>

<li><a href="Nontotient" title="Nontotient">Nontotient</a></li>

<li><a href="Noncototient" title="Noncototient">Noncototient</a></li>

<li><a href="Highly_totient_number" title="Highly totient number">Highly totient number</a></li>

<li><a href="Highly_cototient_number" title="Highly cototient number">Highly cototient number</a></li>

<li><a href="Sparsely_totient_number" title="Sparsely totient number">Sparsely totient number</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-08" href="https://en.wikipedia.org/wiki/?title=Carmichael_function&oldid=1304767304">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>